Some embodiments described herein relate generally to methods and apparatus for implementing a dynamic rate controller in a computer network. In particular, but not by way of limitation, some of the embodiments described herein relate to methods and apparatus for implementing a dynamic rate controller by using linked list pages of rate programs with dynamic scaling of transmission credits and clip values.
A rate controller can distribute guaranteed (G) transmission credits and maximum (M) transmission credits to different network nodes (or devices) and queues associated within different levels in the hierarchy of a network. Rate controllers can determine the transmission rate of data units within a network based on the number of transmission credits provided to each network-node rate counter and queue rate counter in the network and the frequency of each rate update event. Additionally, a clip value can be computed by the rate controller for every node and/or queue in the network and the clip values can be associated by the rate controller to their respective nodes and/or queues in the network. A clip value is associated with each rate update cycle and can limit the accumulation of transmission credits across multiple rate update cycles (e.g., limit data unit burst size). A desirable property of a rate controller is the ability to provide dynamically scaling rate update periods as a function of a dynamically changing size of nodes and queues in a network to minimize jitter and latency in the network. Providing dynamically scaling rate update capability is, however, non-trivial as changes in the rate update period typically involves the rate “instructions” in a rate program to change both the number of transmission credits and the clip value assigned to each node and queue in the network.
Known methods of implementing rate controllers include storing the rate update instructions of a rate program in a memory of a network node (e.g., a router) that is executed by a processor in a single sequence. In such known methods, the rate update period is typically set large enough to accommodate the maximum number of rate update instructions used in the sequence for the largest network configuration. As the configuration of a network changes, distribution of the rate update instructions in a rate program and calculation of transmission credit values and clip values for each node and queue added to the network is performed in every rate update cycle, a process that is computationally intensive. Additionally, in some other known methods, often two rate programs are maintained in the memory of a network node where a first rate program is actively executed and a second rate program is actively rewritten by adding or removing rate update instructions to reflect the network configuration changes. Once the second rate program is updated, it is swapped with the first rate program, typically in a controlled fashion, at the end of a rate update cycle. Such methods of storing multiple rate programs significantly increase the computational resources and memory usage of a network.
Accordingly, a need exists for methods and apparatus for implementing a dynamic rate controller that does not include additional memory space beyond what is used for the rate update instructions and that does not involve added computational resources used for calculating new transmission credit values and clip values in each rate update cycle.